Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7] Example 1: Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Code
int lengthOfLIS(vectori<int>& s)
{
vectori<int>v;
int i,j,n;
n=s.size();
v.push_back(s[0]);
for(i=1;i<n;i++)
{
if(v.back()<s[i])
{
v.push_back(s[i]);
}
else
{
int ind=lower_bound(v.begin(),v.end(),s[i])-v.begin();
v[ind]=s[i];
}
}
return v.size();
}